package JumpFloor;

import jdk.nashorn.internal.runtime.JSONListAdapter;

/**一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 */
public class Solution {
    public static void main(String[] args) {
/*        int i = new Solution().jumpFloor(5);*/
        int i = new Solution().metamorphosisJumpFloor(3);
        System.out.println(i);
    }
    public int jumpFloor(int floorNum){
        if(floorNum > 3 ){
            return jumpFloor(floorNum-1) + jumpFloor(floorNum-2) ;
        }else{
            return floorNum;
        }
    }
    /**
     这就是有一个斐波那契数列，也叫兔子数列， 下一个元素的值，由之前的数列元素决定。
     */
    public int jumpFloor2(int floorNum){
        int rs = 0 ;
        int[] a = new int[floorNum];
        a[1] = 1 ;
        a[2] = 2 ;
        for(int i = 2;i<floorNum;i++){
            a[i] = a[i-1] + a[i-2];
        }
        return rs ;
    }
    /**
     *一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * 分析：jumpFloor 的情况，下一跳只能由两个中可能，一个 a(n-1) ,另外一个是 a(n-2)
     * 在变态的情况下，由 n - 1 中可能。
     * a(n) = a(n-1) + a(n-2) + ... + a(1) + 1;
     * 再进一步的推导，a(n-1) = a(n-2) + ... + a(1) +1;
     * 所以 a(n) = a(n-1) + a(n-1) = 2a(n-1);
     */
    public int metamorphosisJumpFloor(int floorNum){
        int rs = -1 ;
        int[] a = new int[floorNum];
        a[0] = 1;
        a[1] = 2;
        for(int i = 2 ; i < floorNum ; i++){
            a[i] = 2*a[i-1];
        }
        return a[floorNum-1];
    }
    public int metamorphosisJumpFloor2(int floorNum){
        int rs = -1 ;
        int a = 1 ;
        int b  = 0 ;
        for(int i = 2 ; i < floorNum ; i++){
            b = a << 1 ;
            a = b ;

        }
        return b;
    }

}
